package sort;

import java.util.Arrays;

/**
 * 基数排序
 *
 * @author RunningShrimp
 * @date 2021/6/16  15:08
 * @see <a href=""></a>
 */
public class RadixSort extends BaseSort<Integer> {
    @Override
    public void sort(Integer[] array) {
        int maxDigit = getMaxDigit(array);
        radixSort(array, maxDigit);
    }

    /**
     * 获取最高位数
     */
    private int getMaxDigit(Integer[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLength(maxValue);
    }

    private int getMaxValue(Integer[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected int getNumLength(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private void radixSort(Integer[] array, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            Integer[][] counter = new Integer[mod * 2][0];
            for (Integer integer : array) {
                int bucket = ((integer % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], integer);
            }

            int pos = 0;
            for (Integer[] bucket : counter) {
                for (int value : bucket) {
                    array[pos++] = value;
                }

            }
        }
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private Integer[] arrayAppend(Integer[] arr, Integer value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

    public static void main(String[] args) {
        Integer[] array = BaseSort.generateArray(5, 100);
        BaseSort<Integer> sort = new RadixSort();

        System.out.println("排序前：");
        sort.show(array);
        sort.sort(array);
        System.out.println("排序后");
        sort.show(array);
        System.out.println("是否有序：" + sort.isSorted(array));
    }
}
